package com.learn.algorlthm;

/**
 * @classname:
 * @Description:正则表达式匹配
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-07-24 10:34
 * 题目描述：
 *  请实现一个函数用来匹配包括`,`和`*`的正则表达式。模式中的字符`,`表示任意一个字符，而`*`表示它前面的字符可以出现任
 *  意次（包含0次）
 *  在题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa“与模式”a.a" 和"ab*ac*a"匹配，但与"aa.a"和“ab*a"均不匹配
 */
public class Learn19 {

    /**
     * 解题思路
     * 应该注意到，`.`是用来当做一个任意字符，而'*'是用来重复前面的字符。这两个作用不同，不能把`.`的作用和`*`进行类
     * 比，从而把它当成重复前面字符一次。
     */

    public static boolean match(char[] str, char[] pattern) {
        int m = str.length, n = pattern.length;
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0]= true;

        for (int i = 1; i <= n; i++)
            if (pattern[i-1] == '*')
                dp[0][i] = dp[0][i -2];

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (str[m - 1] == pattern[j - 1] ||
                        pattern[j - 1]=='.')
                    dp[i][j] = dp[i - 1][j - 1];
                else if (pattern[j - 1] == '*')
                    if (pattern[j - 2] == str[i - 1] ||
                            pattern[j - 2] == '.') {
                        dp[i][j] |= dp[i][j - 1]; //a* counts as single a
                        dp[i][j] |= dp[i - 1][j]; //a* counts as multiple a
                        dp[i][j] |= dp[i][j - 2]; //a* counts as empty

                    } else {
                        dp[i][j] = dp[i][j - 2]; //a* only counts as empty
                    }

        return dp[m][n];
    }
}
